home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6135 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: news.cyberhighway.net!usenet
  2. From: "Joe E. Coffland" <jcofflan@onyx.idbsu.edu>
  3. Newsgroups: comp.lang.c
  4. Subject: merge algorithm
  5. Date: Thu, 22 Feb 1996 14:30:01 -0800
  6. Organization: none
  7. Message-ID: <312CEE69.842@onyx.idbsu.edu>
  8. NNTP-Posting-Host: pm2-24.cyberhighway.net
  9. Mime-Version: 1.0
  10. Content-Type: text/plain; charset=us-ascii
  11. Content-Transfer-Encoding: 7bit
  12. X-Mailer: Mozilla 2.0b5 (Win16; I)
  13.  
  14. I am trying to find an algorithm to merge two sorted arrays containing
  15. n elements.
  16. ie. A[1] <= A[2]<= ... <= A[m] and A[m+1] <= A[m+2] <= ... <A[n]
  17. The algorithm must run in O(n) time and require only a small amount of
  18. fixed additional memory regardless of the size of m or n. I have reason
  19. to believe that there is such an algorithm but I have only been able to
  20. find algorithms that meet the memory restriction but run in at best
  21. O(nlogn) and are recursive (which can through some work of course be
  22. changed in to an iterative algorithm). If any one can point me to a book
  23. or any other source of information on the subject or just get me headed
  24. in the right direction it would be greatly appriciated.
  25.  
  26. Thank you in advance,
  27. Joe Coffland
  28. please mail to: jcofflan@onyx.idbsu.edu
  29.